package com.binarysearch;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution981 {
    public char nextGreatestLetter(char[] letters, char target) {
        int i = 0;
        int j = letters.length;
        while (i < j) {
            int mid = (i + j) >> 1;
            if (letters[mid] > target) j = mid;
            else i = mid + 1;
        }
        if (j == letters.length) return letters[0];
        return letters[j];
    }
}

class TimeMap {

    class Node {
        String key;
        String value;
        int timestamp;

        public Node(String key, String value, int timestamp) {
            this.key = key;
            this.value = value;
            this.timestamp = timestamp;
        }
    }

    HashMap<String, List<Node>> map = new HashMap<>();

    public TimeMap() {

    }

    public void set(String key, String value, int timestamp) {
        List<Node> nodeList = map.getOrDefault(key, new ArrayList<>());
        nodeList.add(new Node(key, value, timestamp));
        map.put(key, nodeList);
    }

    public String get(String key, int timestamp) {
        List<Node> nodeList = map.getOrDefault(key, new ArrayList<>());
        if (nodeList.isEmpty()) return "";
        int size = nodeList.size();
        int i = 0;
        int j = size - 1;
        while (i < j) {
            int mid = (i + j + 1) >> 1;
            int time = nodeList.get(mid).timestamp;
            if (time <= timestamp) i = mid;
            else j = mid - 1;
        }
        return nodeList.get(i).timestamp <= timestamp ? nodeList.get(i).value : "";
    }
}